#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int j = 0;
        int ret = 0;
        for (; j < prices.size(); j++)
        {
            if (j + 1 < prices.size() && prices[j + 1] > prices[j])
            {
                continue;
            }
            else
            {
                if (i != j)
                {
                    ret += (prices[j] - prices[i]);
                }
                i = j + 1;
            }
        }
        if (i != j)
        {
            ret += (prices[j] - prices[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ret = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] > prices[i - 1])
            {
                ret += (prices[i] - prices[i - 1]);
            }
        }
        return ret;
    }
};

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int m = 0;
        for (auto e : nums)
        {
            if (e < 0)
                m++;
        }
        if (m > k)
        {
            priority_queue<int> q(nums.begin(), nums.begin() + k);
            int ret = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                if (i >= k && nums[i] < q.top())
                {
                    q.pop();
                    q.push(nums[i]);
                }

                ret += nums[i];
            }
            //cout<<ret<<endl;
            while (!q.empty())
            {
                int num = q.top();
                q.pop();
                //cout<<num<<endl;
                num = -num;
                //cout<<num<<endl;
                ret += 2 * num;
            }
            return ret;
        }
        else if (m == k)
        {
            int ret = 0;
            for (auto e : nums)
            {
                if (e < 0)
                {
                    ret += (-e);
                }
                else
                {
                    ret += e;
                }
            }
            return ret;

        }
        else
        {
            int ret = 0;
            int min = nums[0];
            if (min < 0)
                min = -min;
            for (auto& e : nums)
            {
                if (e < 0)
                {
                    e = -e;
                    ret += e;
                }
                else
                {
                    ret += e;
                }
                if (e < min)
                {
                    min = e;
                }
            }
            int n = k - m;
            if (n % 2 == 0)
                return ret;
            //cout<<ret<<endl;
            ret += ((-2 * min));
            //cout<<ret<<endl;
            return ret;
        }
    }
};

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        map<int, string, greater<int>> tmp;
        for (int i = 0; i < names.size(); i++)
        {
            tmp[heights[i]] = names[i];
        }
        vector<string> ret;
        for (auto& e : tmp)
        {
            ret.push_back(e.second);
        }
        return ret;
    }
};

class Solution {
public:
    struct Com
    {
        bool operator()(pair<int, int>& l, pair<int, int>& r)
        {
            return l.first > r.first;
        }
    };
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        vector<pair<int, int>> index;
        for (int i = 0; i < heights.size(); i++)
        {
            index.push_back(make_pair(heights[i], i));
        }
        Com com;
        sort(index.begin(), index.end(), com);
        vector<string> ret;
        for (int i = 0; i < index.size(); i++)
        {
            ret.push_back(names[index[i].second]);
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        vector<int> index(nums2.size(), 0);
        for (int i = 0; i < nums1.size(); i++)
        {
            index[i] = i;
        }
        sort(index.begin(), index.end(), [&](int i, int j)
            {
                return nums2[i] < nums2[j];
            });
        int begin1 = 0, end1 = nums1.size() - 1;
        int begin2 = 0, end2 = nums2.size() - 1;
        vector<int> ret(nums1.size(), 0);
        //int ret = 0;
        for (; begin1 <= end1; begin1++)
        {
            if (nums1[begin1] <= nums2[index[begin2]])
            {
                //cout<<index[end2]<<":"<<nums2[index[end2]]<<":"<<nums1[begin1]<<endl;
                ret[index[end2]] = nums1[begin1];
                end2--;
            }
            else
            {
                //cout<<index[end2]<<":"<<nums2[index[end2]]<<":"<<nums1[begin1]<<endl;
                ret[index[begin2]] = nums1[begin1];
                begin2++;
            }
        }
        return ret;
    }
};